/**
 * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 *
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是）
 *
 * 题目数据保证答案符合 32 位带符号整数范围。
 *

 * 链接：https://leetcode.cn/problems/distinct-subsequences

 */
class NumDistinct {
    public int numDistinct(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int[][] numDis = new int[sLen + 1][tLen + 1];
        numDis[0][0] = 1;
        // F(i,j)，初始化第一行剩余列的所有值为0
        for (int i = 1; i <= tLen; ++i) {
            numDis[0][i] = 0;
        }
        //F(i, 0) = 1
        for (int i = 1; i <= sLen; ++i) {
            numDis[i][0] = 1;
        }
        for (int i = 1; i <= sLen; ++i) {
            for (int j = 1; j <= tLen; ++j) {
                // S的第i个字符与T的第j个字符相同
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    numDis[i][j] = numDis[i - 1][j] + numDis[i - 1][j - 1];
                } else {
                    // S的第i个字符与T的第j个字符不相同
                    // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
                    numDis[i][j] = numDis[i - 1][j];
                }

            }
        }
        return numDis[sLen][tLen];

    }
    /**
     * 空间优化
     */
//    public int numDistinct(String s, String t) {
//        int m=s.length();
//        int n=t.length();
//        int[] dp=new int[n+1];
//        dp[0]=1;
//        for(int i=1;i<=m;i++) {
//            for(int j=n;j>0;j--) {
//                if(s.charAt(i-1)==t.charAt(j-1)) {
//                    dp[j]=dp[j]+dp[j-1];
//                }
//            }
//        }
//        return dp[n];
//    }
}